Pseudo-random number generators (PRNG) are useful in every applications that use Monte Carlo methods and also in cryptography [1]. PRNGs are algorithms implemented on finite-state machines for generating sequences of numbers which appear random-like under many aspects. These sequences are necessarily periodic but their periods are very long, they pass many statistical tests, and they may be easily implemented with simple and fast software routines.
Chaotic systems may be used either in cryptography (see [2Xkjra2001]) and in generating pseudo-random numbers. For example, in a series of papers [3]) a chaos derived pseudo-random number generator has been proposed. It has been numerically observed that the average cycle and transient lengths grow exponentially with the precision of implementation, and from this fact it has been deduced that using high-precision arithmetic it is possible to obtain PRNGs which are still of cryptographic interest. The usual statistical tests applied to PRNGs for use in Monte Carlo simulations are generally simple.
In cryptography, PRNG should not only have good statistical properties, but also be “cryptographically secure”, i.e., given a sequence of pseudo random bits it should be impossible to predict the next number of the sequence with a probability much greater than ½. For this reason, PRNGs suitable for cryptographic applications must pass the next-bit test.
The actual cryptographically secure PRNGs are not computationally efficient. Then they are used only for highly critical off-line operations, while for on-line tasks (like stream ciphers) fast but not cryptographically secure PRNGs are employed. The drawback of this fact is that stream ciphers can be attacked by exploiting the weakness of their PRNGs.
Statistical properties of binary sequences generated by class of ergodic maps with some symmetrical properties are discussed in [4]. The authors derived a sufficient condition for this class of maps to produce a sequence of independent and identically distributed binary random variables. However, the implementation of these maps on finite-state machines and the consequence this implementation may have on the randomness of the generated sequences have not been discussed.
For a better comprehension of a possible field of application of the invention, a brief introduction to the basic concepts of pseudo-random bit generations is provided, according to the approach of [1] (see also [5]).
Definition 1 A (truly) random bit generator is a device which outputs a sequence of statistically independent and unbiased binary digits.
A random bit generator can be used to generate random numbers. For a chaos-based generator of truly random bits see [6].
Definition 2 A pseudo-random bit generator (PRBG) is a deterministic algorithm which, given a truly random binary sequence of length k, outputs a binary sequence of length l>>k which “appears” to be random. The input of the PRBG is called the seed, while the output of the PRBG is called a pseudo-random bit sequence.
Definition 3 A pseudo-random bit generator is said to pass all polynomial-time statistical tests if no polynomial-time algorithm can correctly distinguish between an output sequence of the generator and a truly random sequence of the same length with probability significantly greater than ½.
Definition 4 A pseudo-random bit generator is said to pass the next-bit test if there is no polynomial-time algorithm which, on input of the first I bits of an output sequence s, can predict the (I+1)st bit of s with probability significantly greater than ½.
In this case a PRBG is said unpredictable.
Theorem 1 A pseudo-random bit generator passes the next-bit test if and only if it passes all polynomial-time statistical tests.
Definition 5 Let G={Gn, n≧1} be an ensemble of generators, with Gn:{0,1,}n→{0,1}p(n), where p(*) is a polynomial satisfying n+1≦p(n)≦nc+c for some fixed integer c. We say that G is a cryptographically secure pseudo-random bit generator if                There is a deterministic polynomial-time algorithm that on input of any n-bit string outputs a string of length p(n).        For sufficiently large n, the generator Gn passes the next-bit test.        
All above definitions and the theorem are informal. For a formal definition of statistical test (definition 3), see Yao [7]. The notion of a cryptographically secure pseudo-random bit generator was introduced by Blum and Micali [8]. The theorem 1 (universality of the next-bit test) is due to Yao [7].
The last three definitions above are given in complexity-theoretic terms and are asymptotic in nature because the notion of “polynomial-time” is meaningful for asymptotically large inputs only. Therefore, the security results for a particular family of PRBGs are only an indirect indication about the security of individual members.
Blum and Micali [8] presented the following construction of cryptographically secure PRBG. Let D be a finite set, and let f: D→D be a permutation that can be efficiently computed. Let B: D→{0,1} be a Boolean predicate with the property that B(x) is hard to compute given only x∈D, however, B(x) can be efficiently computed given y=f1(x). The output sequence z1, z2, . . . , zI corresponding to the seed x0∈D is obtained by computing xi=f(xi−1), zi=B(xi), for 1≦i≦I.
Blum and Micali [8] proposed the first concrete instance of cryptographically secure PRBG. Let p be a large prime. Define D=Zp*={1, 2, . . . , p−1} and α a generator of Zp*. The function f: D→D is defined by f(x)=αx mod p. The function B: D→{0, 1} is defined by B(x)=1 if 0≦logαx≦(p−1)/2 and B(x)=0 if logαx≧(p−1)/2. Assuming the intractability of the discrete logarithm problem in Zp*, the Blum-Micali generator was proven to satisfy the next-bit test. Other examples of cryptographically secure PRBGs are RSA generator [9] and Blum-Blum-Shub generator [10].
Linear Congruential Generators
A linear congruential generator produces a pseudo-random sequence of numbers x1, x2, . . . according to the linear recurrencexn=(axn−1+b)mod m, n≧1
Integers a, b and m are parameters which characterize the generator, while x0 is the seed. Generators of this form are widely used in Monte Carlo methods, taking xi/m to simulate uniform draws on [0, 1].
For a study of linear congruential generators, see Knuth [11]. Plumstead [12] and Boyar [13] showed how to predict the output sequence of a linear congruential generator given only a few elements of the output sequence, and when the parameters a, b, and m of the generator are unknown. Boyar [13] extended her methods and showed that linear multivariate congruential generators,xn=(a1xn−1+a2xn−2+ . . . +a1xn−1)mod m and quadratic congruential generators,xn=(axn−12+bxn−1+c)mod m are cryptographically insecure. Krawczyk [14] showed how the output of any multivariate polynomial generator can be efficiently predicted. A truncated linear congruential generator is one where a fraction of the least significant bits of xi are discarded. Frieze et al. [15] showed that these generators can be efficiently predicted if the parameters a, b, and m are known. Stern [16] extended this method to the case where only m is known. Boyar [17] presented an efficient algorithm for predicting linear congruential generators when O(log log m) bits are discarded, and the parameters are unknown.
No efficient prediction algorithms are known for truncated multivariate polynomial congruential generators.